package 贪心;

public class No45跳跃游戏II {

    /**
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     *
     * 示例:
     * 输入: [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     */

    //动态规划
    public int jump(int[] nums) {

        if(nums.length<2){
            return 0;
        }

        int[] dp=new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i]=Integer.MAX_VALUE;
        }

        if(nums[0]>=nums.length){
            return 1;
        }
        //base
        dp[0]=0;
        for (int i = 1; i <= nums[0]; i++) {
            dp[i]=1;
        }

        for (int i = 1; i < nums.length; i++) {

            int count=nums[i];
            for (int j = i+1; j <= i+count; j++) {
                if(j>=nums.length-1){
                    dp[nums.length-1]=Math.min(dp[nums.length-1],dp[i]+1);
                    return dp[nums.length-1];//第一到的则为最少步数
                }else {
                    dp[j] = Math.min(dp[j], dp[i] + 1);
                }
            }

        }

        return dp[nums.length-1];
    }

    //贪心:到本格能跳最远的下标时,就将jump+1,然后设置end为能当前能跳最远的距离,开始往下走
    public int jumpGood(int[] nums){

        int jump=0;
        int end=0;
        int max=0;

        //一定要注意-1,如果到最后一格(题目说必然会跳到最后一格),就会多加一次(比较复杂)
        for (int i = 0; i < nums.length-1; i++) {
            max=Math.max(i+nums[i],max);
            if(end==i){
                jump++;
                end=max;
            }
        }

        return jump;
    }

    public static void main(String[] args) {
        No45跳跃游戏II n=new No45跳跃游戏II();
        int[] arr={1,1,2,1,4};
        int result = n.jumpGood(arr);
        System.out.println(result);
    }

}
